package algdat;

import java.io.File;
import java.io.IOException;
import java.util.Scanner;

/**
 * @author Mikko Puustinen (mikko.puustinen@gmail.com)
 * @version 0.1, 2007-nov-13
 */
public class Ovning32 {

    public Ovning32() throws IOException {
        final Person firstList = readFile("UPPG3B.dat");
        printNames(firstList);
        final Person secondList = readFile("UPPG3A.dat");
        printNames(secondList);
        final Person finalList = merge(firstList, secondList);
        System.out.println("");
        printNames(finalList);
    }

    public static void main(String[] args) throws IOException {
        new Ovning32();
    }

    private Person readFile(String path) throws IOException {
        Person start = null;
        Person p;
        Person prev = null;
        final Scanner scanner = new Scanner(new File(path));

        while (scanner.hasNext()) {
            p = new Person();
            p.name = scanner.nextLine();
            p.next = null;
            if (start == null) {
                start = p;
            } else {
                prev.next = p;
            }
            prev = p;
        }

        scanner.close();

        return start;
    }

    @SuppressWarnings({"ConstantConditions"})
    private Person merge(final Person f, final Person s) {
        Person finalStart = null;
        Person prev = null;
        Person p;
        Person first = f;
        Person second = s;

        while (first != null || second != null) {
            final int result;

            if (first == null) {
                result = 1;
            } else if (second == null) {
                result = -1;
            } else {
                result = first.name.compareToIgnoreCase(second.name);
            }

            if (result < 0) {
                p = first;
                if (finalStart == null) {
                    finalStart = p;
                } else {
                    prev.next = p;
                }
                prev = p;
                first = first.next;
            } else if (result == 0) {
                p = first;
                if (finalStart == null) {
                    finalStart = p;
                } else {
                    prev.next = p;
                }
                prev = p;
                first = first.next;
                second = second.next;
            } else {
                p = second;
                if (finalStart == null) {
                    finalStart = p;
                } else {
                    prev.next = p;
                }
                prev = p;
                second = second.next;
            }
        }
        return finalStart;
    }

    public static void printNames(Person start) {
        Person p = start;

        while (p != null) {
            if (p.next == null) {
                System.out.println(p.name);
            } else {
                System.out.print(p.name + " - ");
            }

            p = p.next;
        }
    }

    private class Person {
        String name;
        Person next;
    }
}
